1. Field of the Invention
The present invention relates to digital data processing systems and more particularly to digital data processing systems characterized by one or more of the following features:
An address space segmented into objects, so that an address of data consists of two parts: an object identifier specifying an object and an offset value specifying a location within the object specified by the object identifier.
Pointers, that is, data which represents addresses, which may represent addresses either directly indirectly. Pointers which represent addresses directly contain addresses; those which represent addresses indirectly contain information which the digital data processing system uses to obtain an address.
Multiple S-languages instead of a single instruction set. An S-language is an intermediate language closely related to a high-level programming language. The meaning of a given operation code in a system with multiple S-languages depends solely on the S-language.
Standard operation code sizes and operand syllable sizes for all S-languages.
Instructions contained in procedures in special objects called procedure objects. Execution of a procedure may be commenced only by a Call instruction.
Instructions which specify locations in memory for data, an operation to be performed on the data, and a destination location in memory for the result of the operations, as opposed to instructions which specify transfers between memory and registers and operations on the contents of the registers.
Call and Return instructions which have the same semantics and manipulate the same data structures in all S-languages.
Base-displacement addressing from base pointers whose values may be changed solely by the execution of Call and Return instructions.
Instructions in which operands are represented by names, that is, indexes into data structures called name tables containing name table entries. In order to obtain the operand's location, the name is resolved, i.e., information in the name's name table entry is combined with the values of the base pointers to produce a descriptor specifying the location, length, and type of the operand represented by the name.
Cache means in the central processing unit for encaching information required to resolve a name.
The present invention may be employed with advantage in any digital data processing system having one or more of the listed characteristics and is particularly advantageous in a digital data processing system having several or all of the above characteristics.
2. Description of the Prior Art
The present data processing systems are an improvement over certain previous digital data processing systems, hereafter referred to as the original data processing systems and described more fully in U.S. Pat. No. 266,539, filed May 22, 1981. The present and original systems have the characteristics listed above and have a number of advantages over traditional digital data processing systems.
Considering first the characteristics shared by the original and present systems, the segmentation of the address space into objects permits an address space which is on the one hand very large, and on the other hand divisible into private address spaces. Which users have access to a given set of objects is determined by a component of the digital data processing system called the access control system.
With regard to the pointers, the existence of pointers which represent addresses either directly or indirectly allows the interpretation of a pointer which represents an address indirectly to be delayed until the actual execution of the program using the pointer. Indeed, though the value of the pointer remains unchanged, the address derived from the value may vary in different executions of the program.
With regard to multiple S-languages, the use of different S-languages corresponding to different high-level languages allows the S-language to be tailored to the high-level language, thereby simplifying the task of compilers and reducing the amount of S-language code produced from a given amount of high-level language code. The complexity of S-language code is further reduced by the use of call and return instructions and instructions which specify operations in terms of the location of data in memory and the operations to be performed on the data and by the use of names to represent operands in the instructions. Since the names refer to name table entries containing location, length, and type information, complicated references are possible in spite of the simplicity of the names. The use of standard sizes for operation codes and operand syllables in all of the S-languages, finally, allows the construction of specialized hardware devices for parsing instructions.
The combination of uniform call and return S-instructions with base-displacement addressing from base pointers whose values may be changed only by a call or a return S-instruction, finally, ensures that a program's addressing environment remains constant throughout the execution of a procedure and allows name table entries to specify locations as offsets from the base pointers.
Experience with the original digital data processing systems of the type described above has, however, revealed a number of problems and shortcomings which reduce the speed and efficiency of execution of programs executed on such systems. These problems and shortcomings involve pointers, names and name table entries, the form of the S-language instructions, the kinds of operations which an opcode in an S-language may specify, the call and return operations, and the resolution of names in a procedure specifying the arguments with which the procedure was invoked.
Beginning with problems associated with object addressing, a pointer which directly specifies an address must specify both an object identifier and an offset, and pointers must therefore contain a large number of bits. Operations involving large pointers are therefore expensive both in terms of fetching and storing the pointers and in terms of processing them. While the extra overhead involved in these operations is not important in the infrequent cases in which a pointer specifies an address indirectly or specifies a location in another object, it interferes markedly with speed and efficiency in the frequent cases in which the pointer simply specifies another address in the object which contains the pointer. Indeed, in these cases, the only relevant information in the pointer is the offset, since the object identifier required for the pointer's value may be obtained from the pointer's own address.
The problems associated with names are similar to those associated with pointers. While a name and its associated name table entry offers a powerful means for dealing with complex references. no name can be resolved without reference to a name table entry and the need to retrieve information from a name table entry markedly increases the number of memory references needed to execute a program. The problems are increased by the fact that a large number of programs do not form complex references and therefore do not need the power provided by the use of names and name table entries. Furthermore, the arrangement of the information in the name table entry is crucial in a digital data system using names, since the length of time required to resolve a name is dependent on the number of fetches from memory required to obtain the information in the name's name table entry.
The problems associated with the S-languages stem from two main sources: first, the physical form of the S-languages is still too complicated to allow the construction of low-cost and efficient hardware parsing devices, and second, the simplicity of the operations described by the S-languages make it difficult to separate certain special types of operations capable of particularly efficient treatment from other operations capable of less efficient treatment.
In the original systems, the S-languages have operation codes of a fixed size, but the operand syllables in a given procedure may have one of a number of sizes. Thus, the hardware parsing device must cope with opcodes and operand syllables which differ in size and with a number of different sizes of operand syllables. Furthermore, it may be necessary to reset the hardware parsing device when a call or return instruction is executed, and it is therefore necessary to save the size of the operand syllables in the calling procedure.
As described above, S-instructions in the original systems specify operations in terms of an operation, locations in memory containing operands for the operation, and a location for the result of the operation. In certain frequent cases, in which the result of a first operation is used immediately as an operand in a second operation, it is more efficient to keep the result of the first operation in the central processing unit, without storing it in memory and retrieving it for the second operation. S-instructions in the original systems have no means of specifying that a result be retained in the central processing unit or that a succeeding S-instruction use the retained result as an operand. Consequently, the S-instruction for the first operation must specify that the result be stored at some location in memory and the S-instruction for the second operation must specify that location as the location of one of the operands. This results in three kinds of inefficiencies: first, additional memory operations are required to store the result of the first operation and fetch it for use in the second operation. Second, additional operand syllables are required to specify the location at which the result of the first operation is to be stored and from which it is to be retrieved, and third, additional memory is required for the temporary storage of the result of the first operation.
Similarly, the use of a single Call instruction requires the inefficient treatment of certain simple cases. At its simplest, a call operation in the original systems requires only the following:
Saving FP, a base pointer specifying the calling procedure's stack frame, SP, a pointer to the top of the calling procedure's stack frame, and the calling procedure's program counter value. PA1 Calculating a new value for the program counter. PA1 Constructing a new frame on the stack for the called procedure and calculating new values for FP and SP.
A return operation need only restore the saved values of the program counter, FP, and SP. Other calls, however, require the retention of much more state. Examples in order of increasing complexity are calls to procedures using different name tables, calls to procedures using different S-languages, calls to procedures contained in different procedure objects, and calls which affect the access control system. Returns from such calls must of course restore the retained state. In the original systems, all Calls and Returns commence as if they are one of the complex cases and do more than is required for the simplest case. Since simple Calls and Returns occur with higher frequency than the others, the result is again slow and inefficient execution of programs.
The fact that names in the original systems are nothing more than indexes of name table entries also prevents maximum use of encachement means for descriptors. Many names in a procedure's S-instructions refer to arguments to the procedure, and these names are resolved by forming a descriptor from a pointer to the argument's location. The pointer to the argument's location must be formed when a call is made and as a linkage pointer, its value will not change during the execution of the called procedure. The pointer is therefore encacheable and the descriptor corresponding to it is available for encachement when the Call S-instruction is executed, but in the original systems, there is no way of determining when the call is made what names the called procedure will refer to the pointers by. Consequently, the pointers cannot be encached when the call is made, but must be encached when a name whose resolution requires the value is presented to the name cache and the value is not present.
The present invention provides data processing system improvements and features which solve the above-described problems and limitations of the original systems.